import { findMaxValue } from '../search/min-max-search';

/**
 * 计数排序：目标数组有n个元素，其中最大值为k；先构造一个长度为k+1的统计数组，
 * 这个统计数组的索引对应着目标数组里的元素值；然后去统计目标数组里每个元素出现
 * 的次数，存储到统计数组对应索引上（次数分布到统计数组里）；最后遍历统计数组，
 * 将其索引当作新项加到新数组里，而“次数”是有几次就给新数组加同样的项几次。
 * @param array 目标数组
 * 值得注意的是，此方法很局限，它适合对小范围的非负整数的数组进行排序；当n不大而
 * k很大时，是不适合使用计数排序的，因为会导致统计数组的长度过长。
 *
 * 计数排序的空间复杂度是O(n+k)，因为它额外使用了一个k+1长的统计数组。最好、平均的
 * 时间复杂度是O(n+k)，最后由统计数组到新数组时，先遍历了k次，再此基础上还总共遍
 * 历了n次插入重复值，最差时间复杂度是O(k)，k远大于n，而n很小。
 */
export function countingSort(array: number[] = []) {
    // 长度小于2就不用排序了
    if (array.length < 2) {
        return array;
    }
    // 目标数组的最大值
    const maxValue = findMaxValue(array);
    // 创建长度为maxValue + 1的统计数组，局限性：目标数组最小值是0最大值是maxValue
    const counts: number[] = new Array(maxValue + 1);
    array.forEach((value: number) => {
        // 第一次需要将undefined置为0，其他次当然为具体数值了
        if (counts[value] == null) {
            counts[value] = 0;
        }
        counts[value] ++;
    });

    // 目标数组的新下标
    let sortedIndex: number = 0;
    // 遍历统计数组，内部再构造一个以次数为标准的循环，依次将数值重新赋给目标数组
    counts.forEach((value: number, index: number) => {
        while (value > 0) {
            // 目标数组的下标要用新的自增值sortedIndex，值的话要用counts的索引index
            array[sortedIndex ++] = index;
            // 赋值后次数减1
            value --;
        }
    });
    return array;
}
